﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleAlgorithms.Tests
{
    /// <summary>
    /// A C# program to print all permutations using Heap's algorithm.
    /// Reference: https://blog.csdn.net/masibuaa/article/details/8171082
    /// </summary>
    public class L11_BackTracking : ITestable
    {
        public void Test()
        {
            int[] a = { 1, 3, 5, 8 };

            // 基于Heap的排列算法
            var results = HeapPermutation(a);

            for (int i = 0; i < results.Count; i++)
                Console.WriteLine($"{i:D2}: {ArrayToString(results[i])}");

            Console.WriteLine("Total: " + results.Count);
        }


        /// <summary>
        /// Generating permutation using Heap Algorithm.
        /// </summary>
        /// <param name="arr">The input array.</param>
        /// <param name="size"></param>
        public List<int[]> HeapPermutation(int[] arr, int size = -1)
        {
            List<int[]> results = new List<int[]>();

            if (size == -1)
                size = arr.Length;

            // if size becomes 1 then prints the obtained permutation
            if (size == 1)
                results.Add(copyArray(arr));


            for (int i = 0; i < size; i++)
            {
                // 
                foreach (var item in HeapPermutation(arr, size - 1))
                    results.Add(copyArray(item));

                Console.WriteLine($"i = {i}, Size={size}, before: {ArrayToString(arr)}");

                // if size is odd, swap 0th i.e (first) and (size-1)th i.e (last) element
                if (size % 2 == 1)
                {
                    int temp = arr[0];
                    arr[0] = arr[size - 1];
                    arr[size - 1] = temp;
                }

                // If size is even, swap ith and  (size-1)th i.e (last) element
                else
                {
                    int temp = arr[i];
                    arr[i] = arr[size - 1];
                    arr[size - 1] = temp;
                }
                Console.WriteLine($"i = {i}, Size={size}, after:  {ArrayToString(arr)}\n");
            }
            return results;
        }


        /// <summary>
        /// Prints the array
        /// </summary>
        /// <param name="a"></param>
        public string ArrayToString(int[] arr)
        {
            return $"[{string.Join(", ", arr)}]";
        }

        public int[] copyArray(int[] arr)
        {
            int[] res = new int[arr.Length];
            for (int i = 0; i < res.Length; i++)
                res[i] = arr[i];
            return res;
        }
    }
}
